Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions. Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and bit shifts.
Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give many-fold speed ups, as bit manipulations are processed in parallel, but the code can become rather more difficult to write and maintain.
Contents |
Bit twiddling and bit bashing are often used interchangeably with bit manipulation, but sometimes exclusively refer to clever or non-obvious ways or uses of bit manipulation, or tedious or challenging low-level device control data manipulation tasks.
The term bit twiddling dates from early computing hardware, where computer operators would make adjustments by tweaking or twiddling computer controls. As computer programming languages evolved, programmers adopted the term to mean any handling of data that involved bit-level computation.
The following two code samples, written in the C++ programming language, both determine if the given unsigned integer x is a power of two.
// The obvious method unsigned int x = ...; bool isPowerOfTwo; if (x > 0) { while ((x % 2) == 0) { x = x / 2; } isPowerOfTwo = (x==1); } else isPowerOfTwo = false;
// A method using bit manipulation bool isPowerOfTwo = x && !(x & (x - 1));
To understand the second method, please note, that powers of two have one and only one bit set in its binary representation:
x == 0...010...0
x-1 == 0...001...1
x & (x-1) == 0...000...0
If the number is not a power of two, it will have '1' in several places:
x == 0...1...010...0 x-1 == 0...1...001...1 x & (x-1) == 0...1...000...0
If inline assembler code is used, then an instruction that counts the number of total 1's or 0's can be used, then a comparison after it. If counting the total 1's, then count must be equal to one for it to be a power of 2 for positive numbers. For example, the x86 instruction POPCNT counts the total number of 1's.
C has direct support for bitwise operations that can be used for bit manipulation. In the following examples, n is the index of the bit to be manipulated within the variable bit_fld, which is an unsigned char being used as a bit field. Bit indexing begins at 0, not 1. Bit 0 is the least significant bit.
bit_fld |= (1 << n)
bit_fld &= ~(1 << n)
bit_fld ^= (1 << n)
bit_fld & (1 << n)
When using an array of bytes to represent set of bits, i.e., a bit array or bitset, the index of the byte in the array associated with a bit n can be calculated using division:
n / CHAR_BIT
where n is the index of the given bit and CHAR_BIT gives the number of bits in a C char.
The index of the bit within the byte indexed by the above can be calculated via a modulo operation:
n % CHAR_BIT
(Note: unsigned char is typically used in C to represent a byte and CHAR_BIT is most often 8 on modern processors. % is the C modulo operator.)